This invention relates to a method for use in a navigation system for finding a shortest path, and more particularly, to a method for finding a shortest overall path length from the start to the final destination when a user of a navigation system wants to visit many intermediate destinations before the final destination.
A navigation system performs travel guidance for enabling a user to easily reach the selected destination. A typical example is a vehicle navigation system. The present invention is not limited to a vehicle navigation system but is applicable to other types of navigation system such as a PDA (Personal Data Assistant), a cellular phone, and other portable navigation devices. However, for the convenience of explanation, the following description is made mainly for the vehicle navigation system.
Such a navigation system detects the position of the vehicle, reads out map data pertaining to an area at the vehicle current position from a data storage medium, for example, a CD-ROM (compact disk read-only memory) or a DVD (digital versatile disc), and displays a map image on a monitor screen (display) while superposing a mark representing the current location of the vehicle on a predetermined portion of the map image. Alternatively, such map data can be provided to the vehicle from a remote server through a communication network such as Internet.
The vehicle position is determined by self-contained navigation sensors (e.g. a distance traveled sensor and a bearing sensor) mounted in the vehicle or by a global positioning system (GPS) including an artificial satellite (satellite navigation). The satellite enables absolute position detection and higher position accuracy than the self-contained navigation sensors. However, the satellite navigation involves a problem of position detection failure such as in a tunnel or a building where the satellite radio signals are obstructed. Therefore, recent navigation systems utilize both self-contained navigation and satellite navigation functions to achieve improved performances.
As the present position of the vehicle changes with the travel of the vehicle, the vehicle current position mark in the map image on the screen is changed accordingly. Alternatively, the map is scrolled while the vehicle current position mark is fixed at a predetermined position, for example, at the center of the image. In either method, the navigation system enables the driver to recognize the map information of the area at the vehicle position at a glance.
When a destination is not set, such a navigation system functions as a locator map which indicates the current location of the vehicle on a map image. When the destination is set, the navigation system starts a route guidance function for setting a guided route from the starting point to the destination. Typically, the route guidance function performs an intersection guidance process in which a monitor screen displays an enlarged intersection diagram and the direction in which the vehicle is to travel while displaying the guide route on a map. When a destination is input, a CPU in the navigation system determines a most suitable guided route from the current vehicle position to the destination and successively stores nodes (expressed in longitude and latitude) constituting the guided route in a memory.
During actual traveling, the node series stored in the memory is searched for a portion of the guided route to be displayed in a map display area of the monitor screen, and the portion of the guided route is highlighted so as to be discriminable from other routes. When the vehicle is within a predetermined distance of an intersection it is approaching, an intersection guidance diagram (an enlarged or highlighted intersection diagram with an arrow indicating the direction in which the vehicle is to turn at the intersection) is displayed to inform a driver of the desired one of roads or directions selectable at the intersection.
FIG. 1A shows an example of a locator map display containing a vehicle current position mark VCP on a map image 21. Typically, a navigation system shows the street on which the vehicle is running in the map image 21 and a name of the street such as xe2x80x9cW 190TH STxe2x80x9d in an information box 23 on the monitor screen. Other information such as a north pointer NP, a map scale and a current time may also be illustrated on the display screen. In this manner, the locator map display shows the current position of the vehicle on the map image, however, it does not perform the route guidance function because the destination is not set in the navigation system.
FIG. 1B shows an example of route guidance display which performs the route guidance function. The route guidance display is activated after specifying the destination. In addition to the map image 21 similar to the locator map of FIG. 1A, this example further shows an arrow indicating the direction (left) in which the vehicle is to turn at the intersection in a guidance information box 22 at the top of the screen. The guidance information box 22 also shows a name of the street xe2x80x9cPRAIRIE AVExe2x80x9d which intersects with the current street xe2x80x9cW 190TH STxe2x80x9d and a distance to the intersection. Thus, the navigation system indicates that the vehicle should make a left turn at the intersection with xe2x80x9cPRAIRIE AVExe2x80x9d.
Typically, the current street xe2x80x9cW 190TH STxe2x80x9d and the left side of the street xe2x80x9cPRAIRIE AVExe2x80x9d will be highlighted in the map image 21. Further, such route guidance is accompanied by voice instructions. If the direction of travel in the next intersection is left, the navigation system gives spoken guidance such as xe2x80x9cturn left at the next intersectionxe2x80x9d. In this example, an information box 24 at the bottom of the display screen includes information regarding the remaining distance to the final destination and an estimated time to reach the final destination.
In order to be guided by the route guidance mode such as shown in FIG. 1B, a destination must be specified in the navigation system so that the system can find one or more routes to get to the destination. FIGS. 2A-2C show examples of display shown on the monitor screen during the operation of inputting the destination.
By operating a menu key, a main menu screen 25 such as shown in FIG. 2A is displayed on the navigation system and a menu item xe2x80x9cDestinationxe2x80x9d is selected from the main menu. This allows the navigation system to display an xe2x80x9cEnter Destination byxe2x80x9d screen 27 as shown in FIG. 2B for specifying an input method for selecting the destination. The xe2x80x9cEnter Destination byxe2x80x9d screen 27 lists various methods for selecting the destination including xe2x80x9cAddressxe2x80x9d for specifying the city and address of the destination, xe2x80x9cIntersectionxe2x80x9d for specifying the names of two streets in the city which intersect with one another, and xe2x80x9cPoint of Interestxe2x80x9d for selecting the programmed destination based on the name, category or telephone number.
Other methods in the xe2x80x9cEnter Destination byxe2x80x9d screen 27 include xe2x80x9cRecent Routexe2x80x9d for specifying the destination based on the recent destinations saved in the navigation system, xe2x80x9cAddress Bookxe2x80x9d for selecting the address of the destination out of the addresses stored in the system, and xe2x80x9cToday""s Planxe2x80x9d for specifying two or more destinations in the navigation system. For example, when a user wants to go to several destinations before the final destination, the navigation system calculates an efficient order and routes to such destinations.
When selecting, for example, the xe2x80x9cAddressxe2x80x9d in FIG. 2B, the navigation system displays an xe2x80x9cEnter Street Namexe2x80x9d screen such as shown in FIG. 2C. The screen of FIG. 2C is basically a key board 38 for inputting the city and address in an address input box 37 on the monitor screen. The user inputs the street name and number in the address input box 37 through the key board 38.
After inputting the destination, the navigation system determines a route to the destination based on, for example, the shortest way to reach the destination, the route using many freeways as possible, or the route without using toll road, and the like. Thus, the navigation system moves to the route guidance display such as shown in FIG. 1B which performs the route guidance.
In the xe2x80x9cToday""s Planxe2x80x9d menu as shown in FIG. 2B, a user specifies two or more destinations through the key board of FIG. 2C or other input methods such as the xe2x80x9cAddress Bookxe2x80x9d or xe2x80x9cRecent Routexe2x80x9d in FIG. 2B. The navigation system finds an efficient route to visit all the destinations until the final destination. For example, to determine the next destination, D the navigation system seeks a next destination which has the shortest distance from the current destination (considering not only physical distances but also travel times and fees, i.e., an overall cost). However, a path determined by a route finding method, such as xe2x80x9cGreedy Algorithmxe2x80x9d in today""s navigation system is not always the best route in terms of finding the shortest overall path length.
FIGS. 3A and 3B show examples of routes calculated by the navigation system when a user want to visit several places before the final destination. In the example of FIG. 3A, the start point xe2x80x9cStartxe2x80x9d, destinations A, B, C and the last destination xe2x80x9cLastxe2x80x9d are shown where the navigation system determines the routes of the tour in the order illustrated by the arrows. Similarly, in the example of FIG. 3B, the start point xe2x80x9cStartxe2x80x9d, destinations A, B, C and D, and the last destination xe2x80x9cLastxe2x80x9d are shown in which the navigation system determines the routes or the tour in the order illustrated by the arrows.
In FIG. 3A, the route between the destinations A and B and the route between the destinations C and Last intersect with one another. Similarly, in FIG. 3B, the path (route segment) between the destinations A and B and the path (route segment) between the destinations D and Last intersect with one another. This means that, in each case, the user has to pass the same point (crossing point) two times, which is considered inefficient for the purpose of traveling the shortest distance. Thus, there is a need of a new method for use in a navigation system for finding a shortest path to the last destination when a user wants to visit several intermediate destinations before reaching the last destination.
It is, therefore, an object of the present invention to provide a method for finding a shortest path for use with a navigation system when a user wants to visit several places before the last destination.
In the present invention, the navigation method and system is designed to find the shortest path when a user has many places to visit. Typically, the user inputs such destinations in the navigation system when using an input method of xe2x80x9cToday""s Planxe2x80x9d such as shown in FIG. 2B. The navigation system calculates the effective ways to visit all of the destinations until the last destination. To determine the next destination, as noted above, the navigation system typically seeks a next destination which has the shortest distance from the current destination. The navigation system then checks whether there is any crossing (intersecting point) involved in the calculated routes. If there is a crossing, the navigation system changes the order of tour to achieve the shortest overall path length to the last destination.
More specifically, the method of the present invention for finding a shortest route of tour having multiple destination includes the steps of: specifying two or more intermediate destinations to visit before a final destination, calculating a route to all of the destinations and tentatively determining an overall route specifying an order of tour of the intermediate destinations before reaching the final destination where the overall route includes two or more route segments each connecting two destinations, checking the overall route as to whether any two route segments intersect with one another, and identifying the destinations of the route segments intersecting one another and reversing the order of destinations of the intersecting route segments so that the two route segments no longer intersect with one another, thereby determining the shortest route of tour.
Another aspect of the present invention is a navigation system configured by various means for achieving the, navigation method described above which checks the order of tour and finds a shortest path when a user wants to visit many places before the last destination.
According to the present invention, the navigation method and system enables the user to visit many intermediate destinations and the final destination through the shortest path.